/**
 * //给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。
 * // 设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小
 * //的直线返回，S[0]相同则选择S[1]值较小的直线返回。
 * // 示例：
 * // 输入： [[0,0],[1,1],[1,0],[2,0]]
 * //输出： [0,2]
 * //解释： 所求直线穿过的3个点的编号为[0,2,3]
 * //
 * // 提示：
 * //
 * // 2 <= len(Points) <= 300
 * // len(Points[i]) = 2
 * //
 * // Related Topics 几何 数组 哈希表 数学 👍 23 👎 0
 */

package com.xixi.medium;

import java.util.HashMap;
import java.util.Map;

public class ID_Interview_16_14_BestLineLcci {
    public static void main(String[] args) {
        Solution solution = new ID_Interview_16_14_BestLineLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /*
         * @Desc: hash method
         * @Author vincentML
         * @Date: 2022/12/27 16:02
         * @param points
         * @return int[]
         */
        public int[] bestLine2(int[][] points) {
            int maxPointSum = 0;
            int[] res = new int[2];
            int n = points.length;
            if (n == 2) return new int[]{0, 1};


            Map<Double, Integer>[] slopeMap = new HashMap[n];
            for (int i = n - 1; i >= 0; --i) {

                slopeMap[i] = new HashMap<>();

                int xA = points[i][0];
                int yA = points[i][1];
                for (int j = n - 1; j > i; --j) { //B → A , A → B are in same line, so don't have to recal them;
                    int xB = points[j][0];
                    int yB = points[j][1];

                    int dx = xA - xB;
                    int dy = yA - yB;

                    double m = dx == 0 ? Double.POSITIVE_INFINITY : dy == 0 ? 0 : (double) dy / dx;

                    int count = slopeMap[j].getOrDefault(m, 1) + 1;

                    slopeMap[i].put(m, count);

                    if (count >= maxPointSum) {
                        maxPointSum = count;
                        res[0] = i;
                        res[1] = j;
                    }

                }


            }


            return res;

        }

        public int[] bestLine(int[][] points) {

            int[] res = new int[]{0, 1};

            int maxNumOfPoint = 2; //记录最大点数
            for (int i = 0; i < points.length; i++) {

                int x1 = points[i][0];
                int y1 = points[i][1];

                for (int j = i + 1; j < points.length; j++) {

                    int x2 = points[j][0];
                    int y2 = points[j][1];
                    int line_Points = 2;

                    //内内循环确定在线上点的个数
                    for (int k = j + 1; k < points.length; k++) {
                        int x3 = points[k][0];
                        int y3 = points[k][1];
                        if ((y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2)) {
                            line_Points++;
                        }
                        if (line_Points > maxNumOfPoint) {
                            res[0] = i;
                            res[1] = j;
                            maxNumOfPoint = line_Points;
                        }
                    }


                }


            }


            return res;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}